// @algorithm @lc id=57 lang=cpp 
// @title insert-interval


// #define print(...)
// @test([[1,3],[6,9]],[2,5])=[[1,5],[6,9]]
// @test([[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8])=[[1,2],[3,10],[12,16]]
// @test([],[5,7])=[[5,7]]
// @test([[1,5]],[2,3])=[[1,5]]
// @test([[1,5]],[2,7])=[[1,7]]
// @test([[1,5]], [0,0])=[[0,0],[1,5]]
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        auto it = intervals.begin();
        for(; it != intervals.end(); it++){
            if(newInterval[1] < (*it)[0]){
                res.push_back(newInterval);
                res.insert(res.end(), it, intervals.end());
                return res;
            }else if((*it)[1] < newInterval[0])
                res.push_back(*it);
            else{
                if((*it)[0] < newInterval[0])
                    newInterval[0] = (*it)[0];
                if(newInterval[1] < (*it)[1])
                    newInterval[1] = (*it)[1];
            }
        }
        if(res.empty() || res.back()[1] < newInterval[0])
            res.push_back(newInterval);
        return res;
    }
};